package algocasts;

public class P87_NumberOfIslands {
    private void dfs(char[][] g, boolean[][] visit, int i, int j) {
        int m = g.length, n = g[0].length;
        if (i < 0 || i >= m || j < 0 || j >= n || g[i][j] == '0' || visit[i][j]) return;
        visit[i][j] = true;
        dfs(g, visit, i - 1, j);
        dfs(g, visit, i + 1, j);
        dfs(g, visit, i, j - 1);
        dfs(g, visit, i, j + 1);
    }

    // Time: O(n*m)  Space: O(n*m)
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 ||
                grid[0] == null || grid[0].length == 0)
            return 0;
        int m = grid.length, n = grid[0].length;
        boolean[][] visit = new boolean[m][n];
        int num = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '0' || visit[i][j]) continue;
                ++num;
                dfs(grid, visit, i, j);
            }
        }
        return num;
    }
}
